#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, k, a[101][101], dp[101][101][101];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            cin >> a[i][j];
    memset(dp, -0x3f, sizeof(dp));
    dp[1][1][0] = a[1][1], dp[1][1][1] = a[1][1] * 3;
    for (int i = 1; i < n; i++)
        for (int j = 1; j <= i; j++)
            for (int l = 0; l <= i; l++){
                dp[i + 1][j + 1][l] = max(dp[i][j][l] + a[i + 1][j + 1], dp[i + 1][j + 1][l]);
                dp[i + 1][j + 1][l + 1] = max(dp[i][j][l] + a[i + 1][j + 1] * 3, dp[i + 1][j + 1][l + 1]);
                dp[i + 1][j][l + 1] = max(dp[i][j][l] + a[i + 1][j] * 3, dp[i + 1][j][l + 1]);
                dp[i + 1][j][l] = max(dp[i][j][l] + a[i + 1][j], dp[i + 1][j][l]);
            }
    int ans = -0x3f3f3f3f;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= k; j++)
            ans = max(ans, dp[n][i][j]);
    cout << ans << endl;
    return 0;
}
